#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

//multipack
int main()
{
    int t;
    cin >> t;
    for (int tt = 0; tt < t; tt++)
    {
        int V, N;
        cin >> V >> N;
        vector<int> val(N, 0);
        vector<int> w(N, 0);
        vector<int> cnt(N, 0);
        vector<int> dp(V + 1, 0);
        for (int i = 0; i < N; i++)
            cin >> w[i] >> val[i] >> cnt[i];

        for (int i = 0; i < N; i++)
        {
            int M = cnt[i];
            if (w[i] * M >= V)
            {
                for (int v = w[i]; v <= V; v++) // complete pack
                    dp[v] = max(dp[v], dp[v - w[i]] + val[i]);
                continue;
            }
            int k = 1;
            while (k < M)
            {
                for (int v = V; v >= k * w[i]; v--) // 01 pack
                    dp[v] = max(dp[v], dp[v - k * w[i]] + k * val[i]);
                M -= k;
                k *= 2;
            }
            for (int v = V; v >= M * w[i]; v--)// 01 pack
                dp[v] = max(dp[v], dp[v - M * w[i]] + M * val[i]);
        }
        cout << dp[V] << endl;
    }
    return 0;
}
